#include <bits/stdc++.h>

using namespace std;

// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/

class Solution 
{
public:
    // 时间复杂度 O(n * logn)，因为有排序，额外空间复杂度 O(logn)
    int numRescueBoats(vector<int>& people, int limit) 
    {
        sort(people.begin(), people.end());
        int ans = 0, l = 0, r = people.size() - 1;
        while(l <= r)
        {
            int sum = l == r ? people[l] : people[l] + people[r];
            if(sum > limit) --r;
            else ++l, --r;
            ++ans;
        }
        return ans;
    }
};